package binary_tree.Leetcode;

public class Num572_Subtree {
    /**
     * 传入两棵树，就能判断subRoot是不是root的子树
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //两棵树都为空  包含
        if(root==null&&subRoot==null){
            return true;
        }
        //两棵树其中一棵树为空 不包含
        if (root==null||subRoot==null){
            return false;
        }
        //判断两棵树是否相同 判断左子树是否包含subroot 右子树是否包含subroot
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||isSameTree(root,subRoot);
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //两棵树都为空
        if(p==null&&q==null){
            return true;
        }
        //有一棵树为空
        if (p == null || q==null){
            return false;
        }
        //p和q都不为空  先判断左右子树是否相同
        if(p.val==q.val){
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }
        return false;
    }
}
